home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / public / agrep / sgrep.c < prev    next >
C/C++ Source or Header  |  1994-08-01  |  18KB  |  685 lines
  1. /* Copyright (c) 1991 Sun Wu and Udi Manber.  All Rights Reserved. */
  2. #include <stdio.h>
  3. #include <ctype.h>
  4. #define MAXSYM  256
  5. #define MAXMEMBER 8192
  6. #define    CHARTYPE    unsigned char
  7. #define MaxError 20
  8. #define MAXPATT 256
  9. #define MAXLINE 1024
  10. #define MaxCan  2048
  11. #define BLOCKSIZE    8192
  12. #define MAX_SHIFT_2  4096
  13. #define ON      1
  14. #define LOG_ASCII 8
  15. #define LOG_DNA  3
  16. #define MAXMEMBER_1 65536
  17. #define LONG_EXAC  20
  18. #define LONG_APPX  24
  19. #define W_DELIM    128
  20.  
  21. extern COUNT, FNAME, SILENT, FILENAMEONLY, num_of_matched;
  22. extern DNA ;  /* DNA flag is set in checksg when pattern is DNA pattern and
  23.          p_size > 16  */
  24. extern WORDBOUND, WHOLELINE, NOUPPER;
  25. extern unsigned char CurrentFileName[],  Progname[]; 
  26. extern unsigned Mask[];
  27. extern unsigned endposition;
  28.  
  29. unsigned char BSize;                /* log_c m   */
  30. unsigned char char_map[MAXSYM];
  31.     
  32.  
  33. /* data area */
  34. int shift_1;
  35. CHARTYPE SHIFT[MAXSYM];
  36. CHARTYPE MEMBER[MAXMEMBER];
  37. CHARTYPE pat[MAXPATT];
  38. unsigned Hashmask;
  39. char MEMBER_1[MAXMEMBER_1];
  40. CHARTYPE TR[MAXSYM];
  41.  
  42. char_tr(pat, m)
  43.     unsigned char *pat;
  44.     int *m;
  45. {
  46. int i;
  47. unsigned char temp[MAXPATT];
  48.     for(i=0; i<MAXSYM; i++) TR[i] = i;
  49.     if(NOUPPER) {
  50.         for(i='A'; i<= 'Z'; i++) TR[i] = i + 'a' - 'A';
  51.     }
  52.     if(WORDBOUND) { /* SUN: To be added to be more complete */
  53.         for(i=0; i<128; i++) {
  54.             if(!isalnum(i)) TR[i] = W_DELIM;
  55.         }
  56.     }
  57.     if(WHOLELINE) {
  58.         memcpy(temp, pat, *m);
  59.         pat[0] = '\n';
  60.         memcpy(pat+1, temp, *m);
  61.         pat[*m+1] = '\n';
  62.         pat[*m+2] = 0;
  63.         *m = *m + 2;
  64.     }
  65. }
  66.  
  67. sgrep(pat, m, fd, D)
  68. CHARTYPE *pat;  int fd, m, D;
  69. { 
  70.     CHARTYPE text[BLOCKSIZE+2*MAXLINE+MAXPATT]; /* input text stream */
  71.     int offset = 2*MAXLINE;
  72.     int buf_end, num_read, i, start, end, residue = 0;
  73.     if(pat[0] == '^' || pat[0] == '$') pat[0] = '\n';
  74.     if(pat[m-1] == '^' || pat[m-1] == '$') pat[m-1] = '\n';
  75.     char_tr(pat, &m);   /* will change pat, and m if WHOLELINE is ON */
  76.     text[offset-1] = '\n';  /* initial case */
  77.     for(i=0; i < MAXLINE; i++) text[i] = 0;   /* security zone */
  78.     start = offset;   
  79.     if(WHOLELINE) start--;
  80.     if(m >= MAXPATT) {
  81.          fprintf(stderr, "%s: pattern too long\n", Progname);
  82.          exit(2);
  83.     }
  84.     if(D == 0) {
  85.     if(m > LONG_EXAC) m_preprocess(pat);
  86.     else prep_bm(pat, m);
  87.     }
  88.     else if (DNA) prep4(pat, m);
  89.      else     if(m >= LONG_APPX) am_preprocess(pat);
  90.         else {
  91.             prep(pat, m, D);
  92.             initmask(pat, Mask, m, 0, &endposition); 
  93.         }
  94.     for(i=1; i<=m; i++) text[BLOCKSIZE+offset+i] = pat[m-1];
  95.         /* to make sure the skip loop in bm() won't go out of bound */
  96.     while( (num_read = read(fd, text+offset, BLOCKSIZE)) > 0) 
  97.     {
  98.        buf_end = end = offset + num_read -1 ;
  99.        while(text[end]  != '\n' && end > offset) end--;
  100.        residue = buf_end - end + 1 ;
  101.        text[start-1] = '\n';
  102.        if(D==0)  {
  103.         if(m > LONG_EXAC) monkey(pat, m, text+start, text+end);
  104.         else bm(pat, m, text+start, text+end);
  105.        }
  106.        else {
  107.         if(DNA) monkey4( pat, m, text+start, text+end, D  );
  108.         else {
  109.           if(m >= LONG_APPX) a_monkey(pat, m, text+start, text+end, D);
  110.           else       agrep(pat, m, text+start, text+end, D);
  111.         }
  112.        }
  113.        if(FILENAMEONLY && num_of_matched) {
  114.             printf("%s\n", CurrentFileName);
  115.             return; }
  116.        start = offset - residue ;
  117.        if(start < MAXLINE) {
  118.             start = MAXLINE; 
  119.        }
  120.        strncpy(text+start, text+end, residue);
  121.        start++;
  122.     } /* end of while(num_read = ... */
  123.     return;
  124. } /* end sgrep */
  125.  
  126. /* SUN: bm assumes that the content of text[n]...text[n+m-1] is 
  127. pat[m-1] such that the skip loop is guaranteed to terminated */
  128.  
  129. bm(pat, m, text, textend)
  130.     CHARTYPE *text, *textend, *pat;  int m;
  131. {
  132. register int shift;
  133. register int  m1, j, d1; 
  134.  
  135. /*
  136. printf("%d\t", textend - text);
  137. printf("%c, %c", *text, *textend);
  138. */
  139.  
  140. d1 = shift_1;    /* at least 1 */
  141. m1 = m - 1;
  142. shift = 0;       
  143. while (text <= textend) {
  144.     shift = SHIFT[*(text += shift)];
  145.     while(shift) {          
  146.         shift = SHIFT[*(text += shift)];
  147.         shift = SHIFT[*(text += shift)];
  148.         shift = SHIFT[*(text += shift)];
  149.     }
  150.         j = 0;
  151.         while(TR[pat[m1 - j]] == TR[*(text - j)]) {
  152.             if(++j == m)  break;       /* if statement can be
  153.                             saved, but for safty ... */
  154.         }
  155.             if (j == m ) { 
  156.             if(text > textend) return;
  157.             if(WORDBOUND) {
  158.                 if(TR[*(text+1)] != W_DELIM) goto CONT;
  159.                 if(TR[*(text-m)] != W_DELIM) goto CONT;
  160.             }
  161.             num_of_matched++;
  162.             if(FILENAMEONLY) return;
  163.             if(!(COUNT)) {
  164.                 if(FNAME) printf("%s: ", CurrentFileName);
  165.                 while(*(--text) != '\n');
  166.                 while(*(++text) != '\n') putchar(*(text));
  167.                 putchar(*text);
  168.             }
  169.             else { while(*text != '\n') text++; } 
  170. CONT:
  171.             shift = 1;
  172.                 }
  173.         else shift = d1;
  174.   }
  175. return;
  176. }
  177.  
  178.   
  179. /* initmask() initializes the mask table for the pattern                    */ 
  180. /* endposition is a mask for the endposition of the pattern                 */
  181. /* endposition will contain k mask bits if the pattern contains k fragments */
  182. initmask(pattern, Mask, m, D, endposition)
  183. CHARTYPE *pattern; unsigned *Mask; register int m, D; unsigned *endposition;
  184. {
  185.   register unsigned Bit1, c;
  186.   register int i, j, frag_num;
  187.  
  188.   Bit1 = 1 << 31;    /* the first bit of Bit1 is 1, others 0.  */
  189.   frag_num = D+1; *endposition = 0;
  190.   for (i = 0; i < frag_num; i++) *endposition = *endposition | (Bit1 >> i);
  191.   *endposition = *endposition >> (m - frag_num);
  192.   for(i = 0; i < m; i++) 
  193.           if (pattern[i] == '^' || pattern[i] == '$') {
  194.               pattern[i] = '\n'; 
  195.           }
  196.   for(i = 0; i < MAXSYM; i++) Mask[i] = ~0;
  197.   for(i = 0; i < m; i++)     /* initialize the mask table */
  198.   {  c = pattern[i];
  199.      for ( j = 0; j < m; j++)
  200.            if( c == pattern[j] )
  201.                Mask[c] = Mask[c] & ~( Bit1 >> j ) ;
  202.   }
  203. }
  204.  
  205. prep(Pattern, M, D)             /* preprocessing for partitioning_bm */
  206.     CHARTYPE *Pattern;  /* can be fine-tuned to choose a better partition */
  207.     register int M, D;
  208. {
  209. register int i, j, k, p, shift;
  210. register unsigned m;
  211. unsigned hash, b_size = 3;
  212.     m = M/(D+1);
  213.     p = M - m*(D+1);
  214.     for (i = 0; i < MAXSYM; i++) SHIFT[i] = m;
  215.     for (i = M-1; i>=p ; i--) {
  216.         shift = (M-1-i)%m;
  217.         hash = Pattern[i];
  218.         if(SHIFT[hash] > shift) SHIFT[hash] = shift;
  219.     }
  220. #ifdef DEBUG
  221.     for(i=0; i<M; i++) printf(" %d,", SHIFT[Pattern[i]]);
  222.     printf("\n");
  223. #endif
  224.     shift_1 = m;
  225.     for(i=0; i<D+1; i++) {
  226.         j = M-1 - m*i;
  227.         for(k=1; k<m; k++) {
  228.             for(p=0; p<D+1; p++) 
  229.                 if(Pattern[j-k] == Pattern[M-1-m*p]) 
  230.                     if(k < shift_1) shift_1 = k;
  231.         }
  232.     }
  233. #ifdef DEBUG
  234.     printf("\nshift_1 = %d", shift_1);
  235. #endif
  236.     if(shift_1 == 0) shift_1 = 1;
  237.     for(i=0; i<MAXMEMBER; i++) MEMBER[i] = 0;
  238.     if (m < 3) b_size = m;
  239.     for(i=0; i<D+1; i++) {
  240.         j = M-1 - m*i;
  241.         hash = 0;
  242.         for(k=0; k<b_size; k++) {
  243.             hash = (hash << 2) + Pattern[j-k];
  244.         }
  245. #ifdef DEBUG
  246.     printf(" hash = %d,", hash);
  247. #endif
  248.         MEMBER[hash] = 1;
  249.     }
  250. }
  251.  
  252.  
  253. agrep( pat, M, text, textend, D ) 
  254. int M, D ; register CHARTYPE *text, *textend, *pat;
  255. {
  256.   register int i;
  257.   register int m = M/(D+1);
  258.   register CHARTYPE *textstart;
  259.   register int shift, HASH;
  260.   int  j=0, k, m1, d1;
  261.   int  n, cdx;
  262.   int  Candidate[MaxCan][2], round, lastend=0;
  263.   unsigned R1[MaxError+1], R2[MaxError+1]; 
  264.   register unsigned int r1, endpos, c; 
  265.   unsigned currentpos;
  266.   unsigned Bit1;
  267.   unsigned r_newline;
  268.  
  269.   Candidate[0][0] = Candidate[0][1] = 0; 
  270.   d1 = shift_1;
  271.   cdx = 0;
  272.   if(m < 3) r1 = m;
  273.   else r1 = 3;
  274.   textstart = text;
  275.   shift = m-1;
  276.   while (text < textend) {
  277.     shift = SHIFT[*(text += shift)];
  278.     while(shift) {
  279.         shift = SHIFT[*(text += shift)];
  280.         shift = SHIFT[*(text += shift)];
  281.     }
  282.         j = 1; HASH = *text;
  283.         while(j < r1) { HASH = (HASH << 2) + *(text-j);
  284.                 j++; }
  285.             if (MEMBER[HASH]) { 
  286.             i = text - textstart;
  287.                          if((i - M - D - 10) > Candidate[cdx][1]) {     
  288.                 Candidate[++cdx][0] = i-M-D-2;
  289.                               Candidate[cdx][1] = i+M+D; }
  290.                          else Candidate[cdx][1] = i+M+D;
  291.             shift = d1;
  292.                 }
  293.         else shift = d1;
  294.   }
  295.  
  296.  
  297.   text = textstart;
  298.   n = textend - textstart;
  299.   r_newline = '\n';
  300.   /* for those candidate areas, find the D-error matches                     */
  301.   if(Candidate[1][0] < 0) Candidate[1][0] = 0;
  302.   endpos = endposition;                /* the mask table and the endposition */
  303.   Bit1 = (1 << 31);
  304.   for(round = 0; round <= cdx; round++)
  305.   {  i = Candidate[round][0] ; 
  306.      if(Candidate[round][1] > n) Candidate[round][1] = n;
  307.      if(i < 0) i = 0;
  308. #ifdef DEBUG
  309.      printf("round: %d, start=%d, end=%d, ", round, i, Candidate[round][1]);
  310. #endif
  311.      R1[0] = R2[0] = ~0;
  312.      R1[1] = R2[1] = ~Bit1;
  313.      for(k = 1; k <= D; k++) R1[k] = R2[k] = (R1[k-1] >> 1) & R1[k-1];
  314.      while (i < Candidate[round][1])                     
  315.      {  
  316.         c = text[i++];
  317.             if(c == r_newline) {
  318.                for(k = 0 ; k <= D; k++) R1[k] = R2[k] = (~0 );
  319.             }
  320.             r1 = Mask[c];
  321.             R1[0] = (R2[0] >> 1) | r1;
  322.             for(k=1; k<=D; k++)
  323.                 R1[k] = ((R2[k] >> 1) | r1) & R2[k-1] & ((R1[k-1] & R2[k-1]) >> 1);
  324.             if((R1[D] & endpos) == 0) { 
  325.                                     num_of_matched++;
  326.                                     if(FILENAMEONLY) { return; }
  327.                                     currentpos = i;
  328.                                     if(i <= lastend) i = lastend;
  329.                                     else {
  330.                                        s_output(text, ¤tpos); 
  331.                                        i = currentpos; 
  332.                                     }
  333.                                     lastend = i;
  334.                                     for(k=0; k<=D; k++) R1[k] = R2[k] = ~0;
  335.                                   }
  336.             c = text[i++];
  337.             if(c == r_newline) {
  338.                 for(k = 0 ; k <= D; k++) R1[k] = R2[k] = (~0 );
  339.             }
  340.             r1 = Mask[c];
  341.             R2[0] = (R1[0] >> 1) | r1;
  342.             for(k = 1; k <= D; k++)
  343.                 R2[k] = ((R1[k] >> 1) | r1) & R1[k-1] & ((R1[k-1] & R2[k-1]) >> 1);
  344.             if((R2[D] & endpos) == 0) { currentpos = i;
  345.                                     num_of_matched++;
  346.                                     if(FILENAMEONLY) { return; }
  347.                                     if(i <= lastend) i = lastend;
  348.                                     else {
  349.                                        s_output(text, ¤tpos); 
  350.                                        i = currentpos; 
  351.                                     }
  352.                                     lastend = i;
  353.                                     for(k=0; k<=D; k++) R1[k] = R2[k] = ~0;
  354.                                   }
  355.      }
  356.   }
  357.   return;
  358. }
  359.  
  360. s_output (text, i) 
  361. int *i; CHARTYPE *text;
  362. {
  363. int kk, bp;
  364.         if(SILENT) return;
  365.         if(COUNT) {
  366.         while(text[*i] != '\n') *i = *i + 1; 
  367.         return;
  368.     }
  369.         if(FNAME == ON) printf("%s: ", CurrentFileName);
  370.         bp = *i;
  371.         while(text[--bp] != '\n');
  372.         while(text[++bp] != '\n') putchar(text[bp]);
  373.         putchar('\n');
  374.         *i = bp;
  375. }
  376.  
  377.  
  378. prep_bm(Pattern, m)      
  379.     unsigned char *Pattern;
  380.     register m;
  381. {
  382. int i, j;
  383. unsigned hash;
  384. unsigned char lastc;
  385.     for (i = 0; i < MAXSYM; i++) SHIFT[i] = m;
  386.     for (i = m-1; i>=0; i--) {
  387.         hash = TR[Pattern[i]];
  388.         if(SHIFT[hash] >= m - 1) SHIFT[hash] = m-1-i;
  389.     }
  390.     shift_1 = m-1;
  391.     lastc = TR[Pattern[m-1]];
  392.     for (i= m-2; i>=0; i--) {
  393.         if(TR[Pattern[i]] == lastc )
  394.             { shift_1 = m-1 - i;  i = -1; }
  395.     }
  396.     if(shift_1 == 0) shift_1 = 1;
  397.     if(NOUPPER) for(i='A'; i<='Z'; i++) SHIFT[i] = SHIFT[i +  'a' - 'A'];
  398. #ifdef DEBUG
  399.     for(i='a'; i<='z'; i++) printf("%c: %d", i, SHIFT[i]); printf("\n");
  400.     for(i='A'; i<='Z'; i++) printf("%c: %d", i, SHIFT[i]); printf("\n");
  401. #endif
  402. }
  403.  
  404.  
  405. /* a_monkey() the approximate monkey move */
  406.  
  407. a_monkey( pat, m, text, textend, D ) 
  408. register int m, D ; register CHARTYPE *text, *textend, *pat;
  409. {
  410. register CHARTYPE *oldtext;
  411. register unsigned hash, i, hashmask, suffix_error; 
  412. register int  m1 = m-1-D, j, pos; 
  413.  
  414.       hashmask = Hashmask;
  415.       oldtext  = text;
  416.       while (text < textend) {
  417.              text = text+m1;
  418.              suffix_error = 0;
  419.              while(suffix_error <= D) {
  420.             hash = *text--;
  421.             while(MEMBER_1[hash]) {
  422.                       hash = ((hash << LOG_ASCII) + *(text--)) & hashmask;
  423.             }
  424.             suffix_error++;
  425.              }
  426.              if(text <= oldtext) {
  427.                    if((pos = verify(m, 2*m+D, D, pat, oldtext)) > 0)  {
  428.                 text = oldtext+pos;
  429.                 if(text > textend) return;
  430.                 num_of_matched++;
  431.                 if(FILENAMEONLY) return;
  432.                 if(!(COUNT)) {
  433.                     if(FNAME) printf("%s: ", CurrentFileName);
  434.                     while(*(--text) != '\n');
  435.                      while(*(++text) != '\n') putchar(*text);
  436.                         printf("\n");
  437.                 }
  438.                 else {
  439.                     while(*text != '\n') text++;
  440.                 }
  441.                }
  442.                else { 
  443.                     text = oldtext + m;
  444.                }
  445.              }
  446.              oldtext = text; 
  447.       }
  448. }
  449.  
  450. /* monkey uses two characters for delta_1 shifting */
  451.  
  452. CHARTYPE SHIFT_2[MAX_SHIFT_2];
  453.  
  454. monkey( pat, m, text, textend  ) 
  455. register int m  ; register CHARTYPE *text, *textend, *pat;
  456. {
  457. register unsigned hash, i; 
  458. register CHARTYPE shift;
  459. register int  m1, j; 
  460. register unsigned r_newline;
  461.  
  462. r_newline = '\n';
  463.  
  464.   m1 = m - 1;
  465.   text = text+m1;
  466.   while (text < textend) {
  467.     hash = *text;
  468.     hash = (hash << 3) + *(text-1);
  469.     shift = SHIFT_2[hash];
  470.     while(shift) {
  471.         text = text + shift;
  472.         hash = (*text << 3) + *(text-1);
  473.         shift = SHIFT_2[hash];
  474.     }
  475.     j = 0;
  476.     while(TR[pat[m1 - j]] == TR[*(text - j)]) { if(++j == m) break; }
  477.     if (j == m ) { 
  478.         if(text >= textend) return;
  479.                 num_of_matched++;
  480.                 if(FILENAMEONLY)  return;
  481.             if(COUNT) {
  482.               while (*text != r_newline) text++;
  483.               text--;
  484.         }
  485.         else {
  486.               if(FNAME) printf("%s: ", CurrentFileName);
  487.                           while(*(--text) != r_newline);
  488.                           while(*(++text) != r_newline) putchar(*text);
  489.               printf("\n");
  490.               text--;
  491.         }
  492.         }
  493.     text++;
  494.   }
  495. }
  496.  
  497. am_preprocess(Pattern)
  498. CHARTYPE *Pattern;
  499. {
  500. int i, j, m;
  501. unsigned hash;
  502.     m = strlen(Pattern);
  503.     for (i = 1, Hashmask = 1 ; i<16 ; i++) Hashmask = (Hashmask << 1) + 1 ;
  504.     for (i = 0; i < MAXMEMBER_1; i++) MEMBER_1[i] = 0;
  505.     for (i = m-1; i>=0; i--) {
  506.         MEMBER_1[Pattern[i]] = 1;
  507.         }
  508.     for (i = m-1; i > 0; i--) {
  509.            MEMBER_1[(Pattern[i] << LOG_ASCII) + Pattern[i-1]] = 1;
  510.     }
  511. }
  512.  
  513.  
  514. verify(m, n, D, pat, text)
  515. register int m, n, D;
  516. CHARTYPE *pat, *text;
  517. {   
  518.     int A[MAXPATT], B[MAXPATT];
  519.     register int last = D;      
  520.     register int cost = 0;  
  521.     register int k, i, c;
  522.     register int m1 = m+1;
  523.     CHARTYPE *textend = text+n;
  524.     CHARTYPE *textbegin = text;
  525.  
  526.    for (i = 0; i <= m1; i++)  A[i] = B[i] = i;
  527.    while (text < textend)
  528.    {
  529.        for (k = 1; k <= last; k++)
  530.        {
  531.            cost = B[k-1]+1; 
  532.            if (pat[k-1] != *text)
  533.            {   if (B[k]+1 < cost) cost = B[k]+1; 
  534.                if (A[k-1]+1 < cost) cost = A[k-1]+1; }
  535.            else cost = cost -1; 
  536.            A[k] = cost; 
  537.        }
  538.        if(pat[last] == *text++) { A[last+1] = B[last]; last++; }
  539.        if(A[last] < D) A[last+1] = A[last++]+1;
  540.        while (A[last] > D) last = last - 1;
  541.        if(last >= m) return(text - textbegin - 1);
  542.        if(*text == '\n') {
  543.             last = D;
  544.         for(c = 0; c<=m1; c++) A[c] = B[c] = c;
  545.        }
  546.        for (k = 1; k <= last; k++)
  547.        {
  548.            cost = A[k-1]+1; 
  549.            if (pat[k-1] != *text)
  550.            {   if (A[k]+1 < cost) cost = A[k]+1; 
  551.                if (B[k-1]+1 < cost) cost = B[k-1]+1; }
  552.            else cost = cost -1; 
  553.            B[k] = cost;
  554.        }
  555.        if(pat[last] == *text++) { B[last+1] = A[last]; last++; }
  556.        if(B[last] < D) B[last+1] = B[last++]+1;
  557.        while (B[last] > D) last = last -1;
  558.        if(last >= m)   return(text - textbegin - 1);
  559.        if(*text == '\n') {
  560.             last = D;
  561.         for(c = 0; c<=m1; c++) A[c] = B[c] = c;
  562.        }
  563.    }    
  564.    return(0);
  565. }
  566.  
  567. /* preprocessing for monkey()   */
  568.  
  569. m_preprocess(Pattern)
  570. CHARTYPE *Pattern;
  571. {
  572. int i, j, m;
  573. unsigned hash;
  574.     m = strlen(Pattern);
  575.     for (i = 0; i < MAX_SHIFT_2; i++) SHIFT_2[i] = m;
  576.     for (i = m-1; i>=1; i--) {
  577.         hash = Pattern[i];
  578.         hash = hash << 3;
  579.         for (j = 0; j< MAXSYM; j++) {
  580.             if(SHIFT_2[hash+j] == m) SHIFT_2[hash+j] = m-1;
  581.         }
  582.         hash = hash + Pattern[i-1];
  583.         if(SHIFT_2[hash] >= m - 1) SHIFT_2[hash] = m-1-i;
  584.     }
  585.     shift_1 = m-1;
  586.     for (i= m-2; i>=0; i--) {
  587.         if(Pattern[i] == Pattern[m-1] )
  588.             { shift_1 = m-1 - i;  i = -1; }
  589.     }
  590.     if(shift_1 == 0) shift_1 = 1;
  591.     SHIFT_2[0] = 0;
  592. }
  593.  
  594. /* monkey4() the approximate monkey move */
  595.  
  596. char *MEMBER_D;
  597.  
  598. monkey4( pat, m, text, textend, D  ) 
  599. register int m, D ; register unsigned char *text, *pat, *textend;
  600. {
  601. register unsigned char *oldtext;
  602. register unsigned hash, i, hashmask, suffix_error; 
  603. register int m1=m-1-D, j, pos; 
  604.  
  605.   hashmask = Hashmask;
  606.   oldtext = text ;
  607.   while (text < textend) {
  608.      text = text + m1;
  609.      suffix_error = 0;
  610.      while(suffix_error <= D) {
  611.     hash = char_map[*text--];
  612.     hash = ((hash << LOG_DNA) + char_map[*(text--)]) & hashmask;
  613.     while(MEMBER_D[hash]) {
  614.           hash = ((hash << LOG_DNA) + char_map[*(text--)]) & hashmask;
  615.     }
  616.     suffix_error++;
  617.      }
  618.      if(text <= oldtext) {
  619.                    if((pos = verify(m, 2*m+D, D, pat, oldtext)) > 0)  {
  620.                 text = oldtext+pos;
  621.                 if(text > textend) return;
  622.                 num_of_matched++;
  623.                 if(FILENAMEONLY) return;
  624.                 if(!(COUNT)) {
  625.                     if(FNAME) printf("%s:", CurrentFileName);
  626.                     while(*(--text) != '\n');
  627.                      while(*(++text) != '\n') putchar(*text);
  628.                         printf("\n");
  629.                     text++;
  630.                 }
  631.                 else {
  632.                     while(*text != '\n') text++;
  633.                     text++;
  634.                 }
  635.                }
  636.                else text = oldtext + m;
  637.      }
  638.      oldtext = text; 
  639.   }
  640. }
  641.  
  642. prep4(Pattern, m)
  643. char *Pattern; int m;
  644. {
  645. int i, j, k;
  646. unsigned hash;
  647.  
  648. for(i=0; i< MAXSYM; i++) char_map[i] = 0;
  649. char_map['a'] = char_map['A'] = 4;
  650. char_map['g'] = char_map['g'] = 1;
  651. char_map['t'] = char_map['t'] = 2;
  652. char_map['c'] = char_map['c'] = 3;
  653. char_map['n'] = char_map['n'] = 5;
  654.  
  655.     BSize = blog(4, m);
  656.     for (i = 1, Hashmask = 1 ; i<BSize*LOG_DNA; i++) Hashmask = (Hashmask << 1) + 1 ;
  657.     MEMBER_D = (char *) malloc((Hashmask+1)  * sizeof(char));
  658. #ifdef DEBUG
  659.     printf("BSize = %d", BSize);
  660. #endif 
  661.     for (i=0; i <= Hashmask; i++) MEMBER_D[i] = 0;
  662.     for (j=0; j < BSize; j++) {
  663.             for(i=m-1; i >= j; i--) {
  664.                hash = 0;
  665.            for(k=0; k <= j; k++) 
  666.           hash = (hash << LOG_DNA) +char_map[Pattern[i-k]]; 
  667. #ifdef DEBUG
  668.            printf("< %d >, ", hash);
  669. #endif
  670.            MEMBER_D[hash] = 1;
  671.             }
  672.         }
  673. }
  674.  
  675. blog(base, m )
  676. int base, m;
  677. {
  678. int i, exp;
  679.     exp = base;
  680.         m = m + m/2;
  681.     for (i = 1; exp < m; i++) exp = exp * base;
  682.     return(i);
  683. }
  684.  
  685.